#coding = utf-8
from collections import deque
from collections import defaultdict

class Graph():
    '''
    无向图
    '''
    def __init__(self):
        self.adj = defaultdict(list)

    def add_edge(self,u,v):
        self.adj[u].append(v)
        self.adj[v].append(u)

class BFSResult:
    def __init__(self):
        self.level = {}
        self.parent = {}

class DFSResult:
    def __init__(self):
        self.parent = {}

def dfs_visit_r(g,v,results,parent=None):
    '''
    :param g: 子节点
    :param v: 目标节点
    :param results:已访问过的结点
    :param parent: 父节点
    :return:
    '''
    results.parent[v] = parent
    for u in g.adj[v]:
        if u not in results.parent:
            dfs_visit_r(g,u,results,v)

def dfs(g):
    results = DFSResult()
    for v in g.adj.keys():
        if v not in results.parent:
            dfs_visit_r(g,v,results)
    return results


def bfs(g:Graph, s)->BFSResult:  # 图 初始节点
    '''
    复杂度为O(E+V)
    :param g:
    :param s:
    :return:
    '''
    r = BFSResult()
    r.level = {s: 0}
    r.parent = {s: None}
    i = 1  # 记录层编号 012
    frontier = [s]
    while frontier:
        next = []
        for u in frontier:
            for v in g.adj[u]:
                if v not in r.level:
                    r.level[v] = i
                    r.parent[v] = u
                    next.append(v)
        frontier = next
        i += 1
    return r

def find_shortest_path(bfs_result:BFSResult,v)->list:
    source_vertex = [verterx for verterx , level in bfs_result.level.items() if level == 0]
    v_parent_list = [v]
    if v != source_vertex[0]:
        v_parent = bfs_result.parent[v]
        v_parent_list.append(v_parent)
        while v_parent != source_vertex[0] and v_parent != None:
            v_parent = bfs_result.parent[v_parent]
            v_parent_list.append(v_parent)
    return v_parent_list

# g = Graph()
# g.add_edge('a','c')
# g.add_edge('c','d')
# g.add_edge('a','b')
# a = bfs(g, 'a')
# print(find_shortest_path(a,'d'))

class Graph1():
    def __init__(self):
        self.adj = defaultdict(list)

    def add_edge(self, u, v):
        for w in v:
            if w in self.adj[u] or len(w) != len(u):
                continue
            match = [i for i in range(len(u)) if w[i] == u[i]]  # 存储相同字符的索引
            if len(match) == len(u) - 1:  # 若相同字符为字符串长度减一 符合变化要求 构造边
                self.adj[u].append(w)
                self.adj[w].append(u)


#1
def find_circle(graph:Graph) -> None:
    results = DFSResult()
    flag = []
    res = []
    for v in graph.adj.keys():
        if v not in results.parent:
            results.parent[v] = None
            if v not in flag:
                stack = [v]
                while stack:
                    u = stack.pop()
                    res.append(u)
                    if u not in flag:
                        flag.append(u)
                    for n in graph.adj[u]:
                        if n in flag and results.parent[u] != n:
                            print("图中有环")
                            res.append(n)
                            print(*res)
                            exit()
                        elif n not in flag:
                            stack.append(n)
                            flag.append(n)
                            results.parent[n] = u
    print("图中无环")


#2
def ergodic_graph(g : Graph) -> list:
    result = []
    flag = {
         "a" : []
        ,"b" : []
        ,"c" : []
        ,"d" : []
        ,"e" : []
    }
    for i in g.adj.keys():
        for j in g.adj[i]:
            if j not in flag[i]:
                result.append(i+j)
                flag[i].append(j)
                flag[j].append(i)
    return result





#最短路径
def find_shortest_path(r, v):
    path = [v, ]
    # 获得源点
    source_vertex = [vertex for vertex, level in r.level.items() if level == 0][0]
    if v != source_vertex:
        while r.parent[v] != source_vertex and r.parent[v] is not None:
            v = r.parent[v]
            path.append(v)
        path.append(source_vertex)
        path.reverse()
        return path



def bfs(g:Graph, s)->BFSResult:  # 图 初始节点
    r = BFSResult()
    r.level = {s: 0}
    r.parent = {s: None}
    i = 1  # 记录层编号 012
    frontier = [s]
    while frontier:
        next = []
        for u in frontier:
            for v in g.adj[u]:
                if v not in r.level:
                    r.level[v] = i
                    r.parent[v] = u
                    next.append(v)
        frontier = next
        i += 1
    return r




if __name__ == '__main__':
    g = Graph()
    g.adj = {
         "a" : ["b","c"]
        ,"b" : ["d","e","a"]
        ,"c" : ["a","e"]
        ,"d" : ["b"]
        ,"e" : ["c","b"]
    }

    #1
    find_circle(g)


    #2
    # res = ergodic_graph(g)
    # print(f'图g有{len(res)}条边,分别为 : ',end='')
    # print(*res)

    #3
    # g = Graph1()
    # dict = ["hot", "dot", "dog", "lot", "log"]
    # start = "hit"
    # end = "cog"
    # dict.extend([start, end])  # 将起始点加入dict 否则构造的图不完整
    # for i in dict:
    #     g.add_edge(i, dict)
    # r = bfs(g, start)
    # print(start + "到" + end + "的最短路径为")
    # print(find_shortest_path(r, end))